1637E - Best Pair - CodeForces Solution

#define __GLIBCXX_DEBUG

#pragma GCC optimize("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

// #define int long long

// DATA TYPES
using ordered_set = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;
using ll = long long;
using ull = unsigned ll;
using ld = long double;

// DEFINES
#define EACH(el, v) for (auto &el : v)
#define SZ(x) (int)x.size()
#define ALL(x) x.begin(), x.end()

// DEBUG
#define debug(x) cout << #x << " = " << x << endl;

#ifdef UWU
mt19937 rnd(228);
#else
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
#endif

long long f(int cnt_1, int cnt_2, set<pair<int, int>>& bad, vector<int>& a, vector<int>& b, int i1, int i2, map<pair<int, int>, long long>& were) {
    if (i1 == a.size() || i2 == b.size()) return -1e9;
    if (were.find({a[i1], b[i2]}) != were.end()) return were[{a[i1], b[i2]}];
    if (a[i1] == b[i2] || bad.find({a[i1], b[i2]}) != bad.end()) {
        were[{a[i1], b[i2]}] = max(f(cnt_1, cnt_2, bad, a, b, i1 + 1, i2, were), f(cnt_1, cnt_2, bad, a, b, i1, i2 + 1, were));
        return were[{a[i1], b[i2]}];
    }
    return 1ll * (cnt_1 + cnt_2) * (a[i1] + b[i2]);
}

void solve() {
    // bad.clear();
    // cnt_x.clear();
    set<pair<int, int>> bad;
    map<int, vector<int>> cnt_x;
    int n, m;
    cin >> n >> m;
    unordered_map<int, int> cnt;
    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        cnt[x]++;
    }
    for (int i = 0; i < m; ++i) {
        int x, y;
        cin >> x >> y;
        bad.insert({x, y});
        bad.insert({y, x});
    }
    for (auto &el : cnt) {
        cnt_x[el.second].push_back(el.first);
    }
    for (auto &el : cnt_x) {
        sort(ALL(el.second));
        reverse(ALL(el.second));
    }
    // for (auto el : cnt_x) {
    //     cout << el.first << " : ";
    //     for (auto ell : el.second) {
    //         cout << ell << ' ';
    //     }
    //     cout << '\n';
    // }
    map<pair<int, int>, long long> were;
    long long ans = 0;
    for (auto &cnt1 : cnt_x) {
        for (auto &cnt2 : cnt_x) {
            if (cnt1.first <= cnt2.first)
                ans = max(ans, f(cnt1.first, cnt2.first, bad, cnt1.second, cnt2.second, 0, 0, were));
        }
    }
    cout << ans << '\n';
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

#ifdef UWU
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    int tests = 1;
    cin >> tests;
    // tests = min(tests, 100);
    while (tests--) {
        solve();
    }
    return 0;
}